// THIS IS THE PROVIDED CODE FOR PROGRAM #2, DSA 1, SPRING 2008

#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <string>
#include <ctime>
#include <cstdlib>

using namespace std;

// A simple class; each object holds five integer values and one string
class Data {
private:
  vector<int> values;
  string code;
public:
  Data() { values.resize(numValues); }
  static const int numValues = 5;
  void setValue(int i, int v) { values.at(i) = v; }
  int getValue(int i) { return values.at(i); }
  void setCode(string s) { code = s; }
  string getCode() { return code; }
};

// Load the data from a specified input file
void loadDataList(list<Data *> &l) {
  string filename;
  cout << "Enter name of input file: ";
  cin >> filename;

  ifstream input(filename.c_str());
  if (!input) {
    cerr << "Error: could not open " << filename << endl;
    exit(1);
  }

  // The first line indicates the size
  int size;
  input >> size;

  // Load the data
  for (int i = 0; i < size; i++) {
    Data *pData = new Data();
    for (int j = 0; j < Data::numValues; j++) {
      int v;
      input >> v;
      pData->setValue(j, v);
    }
    string s;
    input >> s;
    pData->setCode(s);
    l.push_back(pData);
  }

  input.close();
}

// Output the data to a specified input file
void writeDataList(const list<Data *> &l) {
  string filename;
  cout << "Enter name of output file: ";
  cin >> filename;

  ofstream output(filename.c_str());
  if (!output) {
    cerr << "Error: could not open " << filename << endl;
    exit(1);
  }

  // Write the size first
  int size = l.size();
  output << size << endl;

  // Write the data
  for (list<Data *>::const_iterator ipD = l.begin(); ipD != l.end(); ipD++) {
    for (int j = 0; j < Data::numValues; j++) {
      output << (*ipD)->getValue(j) << " ";
      //cout << (*ipD)->getValue(j) << " ";
    }
    output << (*ipD)->getCode() << endl;
    //cout << (*ipD)->getCode() << endl;
  }

  output.close();
}

void sortDataList(list<Data *> &);

// The main function calls routines to get the data, sort the data,
// and output the data.  The sort is timed according to CPU time.
int main() {
  list<Data *> theList;
  loadDataList(theList);

  cout << "Data loaded.  Executing sort..." << endl;

  clock_t t1 = clock();
  sortDataList(theList);
  clock_t t2 = clock();
  double timeDiff = ((double) (t2 - t1)) / CLOCKS_PER_SEC;

  cout << "Sort finished. CPU time was " << timeDiff << " seconds." << endl;

  writeDataList(theList);
}

// -------------------------------------------------
// YOU MAY NOT CHANGE OR ADD ANY CODE ABOVE HERE !!!
// -------------------------------------------------
#include <math.h>

list<Data*>::iterator get_element_at_index(int index, list<Data *> &l);
void QuickSort(list<Data *> &l, int first, int last);
list<Data*>::iterator GetPivot(list<Data *> &l, int firstElementIndex, int lastElementIndex);
int compare(list<Data*>::iterator leftfirst_itr,list<Data*>::iterator rightfirst_itr);
int compare(Data* leftDataValue, Data* rightDataValue);
void SwapValues(list<Data*>::iterator &leftfirst_itr, list<Data*>::iterator &rightfirst_itr);
Data *temparray[99167];

ofstream outputFile;

void sortDataList(list<Data *> &l) {
	/*list<Data *>::iterator itr;
	itr = get_element_at_index(99167,l);
	cout <<(*itr)->getValue(1)<<endl;*/
	
   // Driver for Merge Sort
   //mergesort(l,1,l.size());

   outputFile.open("partitionResult.txt");
   //Driver for Quick Sort
   QuickSort(l, 1, l.size());
}

void QuickSort(list<Data *> &l, int firstElementIndex, int lastElementIndex){
   if(firstElementIndex + 2 <= lastElementIndex){
      list<Data*>::iterator pivot = GetPivot(l, firstElementIndex, lastElementIndex);
      
      //Begin partitioning
      int i = firstElementIndex, j = lastElementIndex - 1;
      for (;;){
         //cout << "looping" <<endl;
         while ( compare(get_element_at_index(++i, l), pivot) == -1) { }      //keep moving the left tracker as long as elements are smaller than pivot
         while ( compare(pivot, get_element_at_index(--j, l)) == -1) { }      //keep moving the right tracker as long as elements are bigger than pivot
         if ( i < j ) {
            list<Data*>::iterator leftValue = get_element_at_index(i, l);
            list<Data*>::iterator rightValue = get_element_at_index(j, l);
            SwapValues(leftValue, rightValue);
         }else{
            break;
         }
      }
     
      //cout << "Swapping pivot and partitioning" << endl; 
      list<Data*>::iterator leftValue = get_element_at_index(i, l);
      SwapValues(leftValue, pivot);

      //writeDataList(l);
      outputFile << "left partition size: " << (i-1) << " right partition size: " << (lastElementIndex-i-1) <<endl;
      QuickSort(l, firstElementIndex, i - 1);
      QuickSort(l, i + 1, lastElementIndex);
   }else{
      /* 
         NOTE: Leaving Insertion sort out as sort time reduced by ~4secs if I used quicksort till 3 elements 
         and then used manual compare+swap for two elements
      */
      if(firstElementIndex < lastElementIndex){
         list<Data*>::iterator leftValue = get_element_at_index(firstElementIndex, l);
         list<Data*>::iterator rightValue = get_element_at_index(lastElementIndex, l);
         
         if(compare(leftValue, rightValue) == 1){
            SwapValues(leftValue, rightValue);
         }
      }
      /*
      // Perform Insertion sort
      for (int ctr = firstElementIndex + 1; ctr <= lastElementIndex; ctr++){

         //cout << "Running insertion sort" << endl;
         list<Data*>::iterator valueToSortAsItr = get_element_at_index(ctr, l);
         Data* valueToSortAsPtr = *valueToSortAsItr;
         //cout << "ctr: " << ctr << "value " << (*valueToSortAsItr)->getValue(0) << endl;
         
         int trackingIndex = ctr - 1;
         while ((trackingIndex > 0) && (compare(*(get_element_at_index(trackingIndex, l)), valueToSortAsPtr) == 1)){
            list<Data*>::iterator valueToMove = get_element_at_index(trackingIndex, l);
            list<Data*>::iterator nextValue = get_element_at_index(trackingIndex + 1, l);
            *nextValue = *valueToMove;
            trackingIndex = trackingIndex - 1;
            //cout << valueToSortAsPtr->getValue(0) << endl;
         }
        
         list<Data*>::iterator positionOfValueToSort = get_element_at_index(trackingIndex + 1, l);
         *positionOfValueToSort = valueToSortAsPtr;
         //writeDataList(l);
      }
      */ 
   }
   outputFile.close();
}

// Get pivot using median-of-three partitioning
list<Data*>::iterator GetPivot(list<Data *> &l, int firstElementIndex, int lastElementIndex){
   int centerIndex = ( firstElementIndex + lastElementIndex ) /2;
   list<Data*>::iterator leftElement = get_element_at_index(firstElementIndex, l);
   list<Data*>::iterator rightElement = get_element_at_index(lastElementIndex, l);
   list<Data*>::iterator centerElement = get_element_at_index(centerIndex, l);

   if( compare(centerElement, leftElement) == -1){
     SwapValues(centerElement, leftElement); 
   }
   if( compare(rightElement, leftElement) == -1){
      SwapValues(rightElement, leftElement);
   }
   if( compare(rightElement, centerElement) == -1){
      SwapValues(rightElement, centerElement);   
   }

   list<Data*>::iterator pivotElement = get_element_at_index(lastElementIndex-1, l);
   SwapValues(centerElement, pivotElement);

   //cout << "Pivot is: " << (*pivotElement)->getValue(0) << endl;
   return pivotElement;
}


// Overloaded compare method
int compare(list<Data*>::iterator leftfirst_itr,list<Data*>::iterator rightfirst_itr){
   compare(*leftfirst_itr, *rightfirst_itr);
}



// Compare provided values and return
// -1 if left side is smaller than right side
// 1 if right side is smaller than left side
// 0 if both are equal
int compare(Data* leftDataValue, Data* rightDataValue){
   int pos = 0;
   int result = -500;
   for(int pos = 0; pos < 5; pos++){
      int leftValue = leftDataValue->getValue(pos);
      int rightValue = rightDataValue->getValue(pos);
      //cout << "Comparing: Left Element:" << leftValue << " and right Element:" << rightValue << endl;
	   if(leftValue < rightValue){
         result = -1;        // left side is smaller
         break;
	   }else if(leftValue > rightValue){
	      result = 1;         // right side is smaller
         break;
      }else{
		   result = 0;      // equal
	   }
   }
   if(!result){
      //cout << "all numbers equal" <<   endl;
      string leftString = leftDataValue->getCode();
      string rightString = rightDataValue->getCode();
      if (leftString < rightString){
         result = -1;
      }else if(leftString > rightString){
         result = 1;
      }
   }
   //cout << "Comparison Result:" << result << endl;
   return result;
}

// Swap provided values
void SwapValues(list<Data*>::iterator &leftfirst_itr, list<Data*>::iterator &rightfirst_itr){
   Data* temp = *leftfirst_itr;
   *leftfirst_itr = *rightfirst_itr;
   *rightfirst_itr = temp;
}


list<Data*>::iterator get_element_at_index(int index, list<Data *> &l){
	list<Data *>::iterator itr;
	itr = l.begin();
	//cout <<"==>"<<(*itr)->getValue(0)<<endl;
	int ctr;
	
	for(ctr=0; ctr < index; ctr++){
		//cout <<ctr<<"==>"<<(*itr)->getValue(1)<<endl;
		itr++;
	}
	//since the iterator is ahead of the ctr 
	itr--;
	//cout <<ctr<<"==>"<<(*itr)->getValue(0)<<endl;
	return itr;
}


//**************************************************
//MERGE SORT
//**************************************************

/*
void mergesort(list<Data *> &l, int first, int last){
	if(first < last){
		//cout <<"mergesort"<<endl;
		//cout <<first<<"--"<<last<<endl;
		int mid = (first + last)/2;
		mergesort(l,first,mid);
		mergesort(l,mid+1,last);
		merge(l,first,mid,mid+1,last);
	}
}

void merge(list<Data *> &l, int leftfirst, int leftlast, int rightfirst, int rightlast){
	//cout <<"merge"<<leftfirst<<"-"<<leftlast<<"-"<<rightfirst<<"-"<<rightlast<<endl;
	int index2 = leftfirst-1;
	int start = leftfirst;
	list<Data *>::iterator leftfirst_itr = get_element_at_index(leftfirst,l);
	list<Data *>::iterator rightfirst_itr = get_element_at_index(rightfirst,l);
	//cout<<"::"<<endl;
	//cout <<(*leftfirst_itr)->getValue(0)<<"@@"<<(*rightfirst_itr)->getValue(0)<<endl;
	while((leftfirst <= leftlast) && (rightfirst <= rightlast)){
		compare(leftfirst_itr,rightfirst_itr,0,leftfirst,rightfirst,index2);
		index2++;
	}
	while(leftfirst <= leftlast){
		//cout<<"copyleft"<<endl;
		temparray[index2] = (*leftfirst_itr);
		leftfirst_itr++;
		leftfirst++;
		index2++;
	}
	while(rightfirst <= rightlast){
		//cout<<"copyright"<<endl;
		temparray[index2] = (*rightfirst_itr);
		rightfirst_itr++;
		rightfirst++;
		index2++;
	}
	list<Data*>::iterator itr=get_element_at_index(start,l);
	for(int index = (start-1); index < rightlast; index++){
		//cout <<index<<"~~";
		(*itr)=temparray[index];
		//cout<<temparray[index]->getValue(0);
		itr++;
	}
	cout <<endl;
}

void compare(list<Data*>::iterator &leftfirst_itr,list<Data*>::iterator &rightfirst_itr,int pos,int &leftfirst, int &rightfirst,int index2){
	//cout <<"compare";
	//cout <<index2<<"**"<<endl;
	if((*leftfirst_itr)->getValue(pos) < (*rightfirst_itr)->getValue(pos)){
		temparray[index2] = (*leftfirst_itr);
		//cout<<(*leftfirst_itr)->getValue(0)<<"+"<<temparray[index2]->getValue(0);
		leftfirst_itr++;
		leftfirst++;
	}else if((*leftfirst_itr)->getValue(pos) > (*rightfirst_itr)->getValue(pos)){
		temparray[index2] = (*rightfirst_itr);
		//cout<<(*rightfirst_itr)->getValue(0)<<"+"<<temparray[index2]->getValue(0);
		rightfirst_itr++;
		rightfirst++;
	}else{
		if(pos == 4){
			temparray[index2] = (*leftfirst_itr);
			leftfirst_itr++;
			leftfirst++;
		}else{
			pos++;
			compare(leftfirst_itr,rightfirst_itr,pos,leftfirst,rightfirst,index2);
		}
	}
	cout<<endl;
}

list<Data*>::iterator get_element_at_index(int index, list<Data *> &l){
	list<Data *>::iterator itr;
	itr = l.begin();
	//cout <<"==>"<<(*itr)->getValue(0)<<endl;
	int ctr;
	
	for(ctr=0; ctr < index; ctr++){
		//cout <<ctr<<"==>"<<(*itr)->getValue(1)<<endl;
		itr++;
	}
	//since the iterator is ahead of the ctr 
	itr--;
	//cout <<ctr<<"==>"<<(*itr)->getValue(0)<<endl;
	return itr;
}
*/

//**************************************************
//BUBBLE SORT
//**************************************************

// You may add functions or class defintions here if you wish
/*void swap(Data *item1, Data *item2);

void sortDataList(list<Data *> &l) {
  // Fill in this function
	list<Data *>::iterator itr;
	itr = l.begin();
	
	int current=0;
	int numvalues = l.size();
	while(current < numvalues){
		for(int i=current; i < (numvalues-1); i++){
			Data *temp1 = (*itr++);
			Data *temp2 = (*itr);
			if((temp1->getValue(0)) > (temp2->getValue(0))){
				swap(*temp1,*temp2);
			}
			if((temp1->getValue(0)) == (temp2->getValue(0))){
				if((temp1->getValue(1)) > (temp2->getValue(1)))
					swap(*temp1,*temp2);
				if((temp1->getValue(1)) == (temp2->getValue(1))){
					if((temp1->getValue(2)) > (temp2->getValue(2)))
						swap(*temp1,*temp2);
					if((temp1->getValue(2)) == (temp2->getValue(2))){
						if((temp1->getValue(3)) > (temp2->getValue(3)))
							swap(*temp1,*temp2);
						if((temp1->getValue(3)) == (temp2->getValue(3))){
							if((temp1->getValue(4)) > (temp2->getValue(4)))
								swap(*temp1,*temp2);
						}		
					}	
				}	
			}
			
		}
		itr=l.begin();
		numvalues--;
	}
	
}

void swap(Data &item1, Data &item2){
	Data temp;
	temp = item1;
	item1  = item2;
	item2= temp;
	
}*/
